package leetcode_1701_1800;

public class LeeCode_1745 {
    public static void main(String[] args) {
        System.out.println(checkPartitioning("abcbdd"));
        System.out.println(checkPartitioning("acbc"));
    }
    private static boolean checkPartitioning(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        boolean[][] tab = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            int l = i, r = i;
            while (l >= 0 && r < n && s[l] == s[r]){
                tab[l][r] = true;
                l--;
                r++;
            }
            l = i;
            r = i + 1;
            while (l >= 0 && r < n && s[l] == s[r]){
                tab[l][r] = true;
                l--;
                r++;
            }
        }
        for (int i = 0; i < n - 2; i++) {
            if (tab[0][i]){
                for (int j = i + 1; j < n - 1; j++) {
                    if (tab[i + 1][j] && tab[j + 1][n - 1]){
                        return true;
                    }
                }
            }
        }
        return false;
    }
}